/**
 * 非循环双链表l（有头节点）
 * l的有一个freq字段用来记录访问的次数
 * l要求按照freq字段降序排列
 */

class CircleLinkedList
{
public:
    int data;
    CircleLinkedList *next;
    CircleLinkedList *prior;
    int freq=0;
    CircleLinkedList();
    ~CircleLinkedList();
};


/**
 * 找到x
 * 将x摘下来
 * 从这个节点的往前找（这个是双向链表，找到第一个频率比他大的，插入到这个节点的后面）
 */
CircleLinkedList* locate(CircleLinkedList *l,int x){
    CircleLinkedList *p=l->next,*q;//p是工作指针，q是p的前驱
    while (p&&p->data!=x)//如果不是x，就往后查找
    {
        p=p->next;
    }
    if(!p){//如果最后p为空，说明没有找到
        return;
    }else{//找到了x，p就是x的指针
        p->freq++;//访问次数+1
        //p的前驱是l的话，说明这个节点就是第一个节点，就不用操作了
        //或者p的前一个访问次数和当前的访问次数相同，就不用往前移动了
        if(p->prior==l|| p->prior->freq==p->freq ){
            return p;
        }
        //如果p的下一个不是空，将p从链中摘下来
        //if下面的那两个语句也会执行
        if(p->next!=nullptr){
            p->next->prior=p->prior;
        }
        p->prior->next=p->next;
        q=p->prior;//q初始化为p的前驱，然后不断移动，找到适合插入的位置
        while (q!=l&&q->freq<p->freq)
        {
            q=q->prior;
            p->next=q->next;//找到了比x大的节点，将p连接上去
            if(q->next!=nullptr) q->next->prior=p;
            p->prior=q;
            q->next=p;
        }
        
    }
    return p;
}